package com.ds.map_set.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/10/9 9:02
 */
public class Num138_RandomList2 {
    public Node copyRandomList(Node head) {
        // 1.遍历原链表，构造Map集合维护原链表节点和新链表结点的映射关系
        // 原1 = 新1
        Map<Node,Node> map = new HashMap<>();
        for (Node x = head;x != null;x = x.next) {
            Node node = new Node(x.val);
            map.put(x,node);
        }
        // 2.再次遍历原链表，通过映射关系维护新链表的next和random
        for (Node x = head;x != null;x = x.next) {
            // 原1.next = 原3
            // 新1.next = 新3
            map.get(x).next = map.get(x.next);
            // 原1.random = 原5
            // 新1.random = 新5
            map.get(x).random = map.get(x.random);
        }
        // 新1 => 原1
        return map.get(head);
    }
}

